package com.sss.hloster02;

public class BinarySearch {

	public static void main(String[] args) {
		int[] arr = { 6, 12, 33, 87, 90, 97, 108, 561 };
		System.out.println("循环查找：" + (binarySearch(arr, 87)));
		System.out.println("递归查找：" + binarySearch(arr, 12, 0, arr.length - 1));
	}

	public static int binarySearch(int[] arr, int x) {
		int low = 0;
		int high = arr.length - 1;
		while (low <= high) {
			int middle = (low + high) / 2;
			if (x == arr[middle]) {
				return middle;
			} else if (x < arr[middle]) {
				high = middle - 1;
			} else {
				low = middle + 1;
			}
		}
		return -1;
	}

	// 递归实现二分查找
	public static int binarySearch(int[] arr, int data, int begin, int end) {
		//返回值，默认为-1，表示没有找到
		int index=-1;
		//结束条件：没有找到
		if(begin>end) {
			//没有找到，递归结束
			return  index;
		}
		//取出中间元素
		int mid =(begin+end)/2;
		//取出中间元素的值
		int midVal=arr[mid];
		//结束条件：找到相应值
		if(data == midVal) {
			//找到相应位置，返回找到的位置
			return mid;
		}else if(data>midVal) {
			//继续递归调用，递归右半部分
			return binarySearch(arr,data,mid+1,end);
		}else {
			//继续递归调用，递归左半部分
			return binarySearch(arr,data,begin,mid-1);
		}
	}

	private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
		int low = fromIndex;
		int high = toIndex - 1;
		while (low <= high) {
			int mid = (low + high) >>> 1;
			long midVal = a[mid];
			if (midVal < key) {
				low = mid + 1;
			} else if (midVal > key) {
				high = mid - 1;
			} else {
				return mid;
			}			
		}
		return -(low + 1);
	}
}
